package com.example.demo.zaqizabatest.leetcode.day5;

import java.util.TreeSet;

/**
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，
 * 每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，
 * 输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
@SuppressWarnings("AlibabaLowerCamelCaseVariableNaming")
public class Solution1 {




    public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0) {
            return false;
        }
        int m = matrix.length, n = matrix[0].length;
        int row = 0, col = n - 1;
        while(row < m && col >= 0) {
            if(matrix[row][col] > target) {
                col--;
            }else if(matrix[row][col] < target) {
                row++;
            }else {
                return true;
            }
        }
        return false;



//        if (matrix.length == 0)
//            return false;
//        // 行数
//        int row = matrix.length;
//        // 列数
//        int col = matrix[0].length;
//
//        if (row == 1) {
//            int[] onlyOneRow = matrix[0];
//            int i = Arrays.binarySearch(onlyOneRow, target);
//            if (i < 0)
//                return false;
//            return true;
//        }
//
//        if (col == 1) {
//            int[] onlyOneCol = new int[row];
//            for (int i = 0; i < row; i++) {
//                onlyOneCol[i] = matrix[i][0];
//            }
//            int j = Arrays.binarySearch(onlyOneCol, target);
//            if (j < 0)
//                return false;
//            return true;
//        }
//        return binarySearchIn2DArray(matrix, 0, row -1, 0 ,col -1, target);
    }

    private static boolean binarySearchIn2DArray(int[][] matrix, int rowLow, int rowHigh, int colLow, int colHigh, int
            target) {
        TreeSet<Integer> set = new TreeSet<>();
        for (; rowLow <= rowHigh; rowLow++ ){
            for (; colLow <= rowHigh; colHigh++ ){
                set.add(matrix[rowLow][colLow]);
            }
        }
        if (set.contains(target)) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] a = new int[][]{
                {1,4},
                {2,5}};
        System.out.println(findNumberIn2DArray(a, 2));
    }

}
